Autostrady

Limit pamięci: 32 MB

Drogi w Dalekim Kraju są w bardzo złym stanie, ale pozwalają na dotarcie z każdego miasta do dowolnego innego (choć może to wymagać odwiedzenia wielu miast). Żeby temu zaradzić rząd Dalekiego Kraju postanowił wybudować autostrady. Z braku pieniedzy zdecydowano się na budowę najmniejszej możliwej liczby autostrad, które umożliwią przejazd pomiędzy dwoma dowolnymi miastami. Autostrady mają być zbudowane w miejsce istniejących (wybranych) dróg. Znany jest koszt przebudowy każdej drogi. Okazało się, że koszty przebudowy różnych dróg są różne. Autostrady mają zbudować prywatne przedsiębiorstwa za pieniądze publiczne. Rząd wie, że opinię społeczną nie tyle interesuje łączny koszt wybudowania wszystkich autostrad, ale to ile zarobią poszczególne przedsiebiorstwa. Dlatego zdecydowano się na wybudowanie takiej sieci autostrad, żeby koszt najdroższej z nich był jak najmniejszy. Jaki jest koszt budowy najdroższej autostrady przy takim założeniu? Wszystkie drogi i autostrady są dwukierunkowe.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis systemu drogowego w Dalekim Kraju i koszty przebudowy poszczególnych dróg na autostrady,
• obliczy koszt budowy najdroższej autostrady przy założeniu, że wybuduje się ich jak najmniej, zapewniając jednocześnie przejazd autostradami pomiędzy dowolnymi dwoma miastami oraz że koszt budowy najdroższej z nich będzie jak najmniejszy,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu podane są dwie liczby całkowite (), oddzielone pojedynczym odstępem. Liczba jest liczbą miast w Dalekim Kraju. Miasta są ponumerowane od 1 do . Liczba jest liczbą dróg. Każda droga łączy bezpośrednio dwa miasta. Każdy z następnych wierszy zawiera trzy liczby całkowite opisujące jedną drogę wraz z kosztem jej przebudowy. Liczby oddzielone są pojedynczymi znakami odstępu. Dwie pierwsze liczby są numerami miast, które ta droga łączy, natomiast trzecia liczba jest kosztem przebudowy drogi na autostradę. Koszt pojedyczej przebudowy jest dodatnią liczbą całkowitą nie większą niż .

Wyjście

Pierwszy i jedyny wiersz powinien zawierać koszt budowy najdroższej autostrady przy spełnieniu warunków zadania.

Przykład

Dla danych wejściowych:

10 19
10 7 9
7 10 100
10 7 77
5 4 3
3 9 4
3 5 6
1 4 1
10 1 7
8 9 8
2 9 3
10 5 5
8 10 6
3 1 9
5 2 7
2 3 2
7 4 8
10 4 1
5 6 1
10 6 2

poprawną odpowiedzią jest:

8